#define  _CRT_SECURE_NO_WARNINGS 1

#include"head.h"

//求n的阶乘

int factorial(int n)
{
	if (n == 0)
	{
        return 1;
	}
	else if (n > 0)
	{
        return n * factorial(n - 1);//递归
	}
    else
    {
        printf("输入的数字有误！");
        return 404;
    }
}

//递归的每次调用都会创建一个新的栈帧，对内存的占用会变大

//迭代(循环)实现效率更高，内存占用更小
int factorial_2(int n)
{
    int i = 1;
    int result = 1;
    while (i <= n)
    {
        result *= i;
        i++;
    }
    return result;
}

int factorial_3(int n)
{
    int i = 0;
    int ret = 1;
    for (i = 1; i <= n; i++)
    {
        ret *= i;
    }
    return ret;
}

//1.迭代（循环）
// 有时候代码写起来比较复杂；
// 效率高。
// 
//2.递归
// 简洁；
// 有时候运行开销较大，可能会影响效率，或者栈溢出
// 
//合理取舍，哪个适合用哪个
// 
// 要列公式
// 

//================================================

//顺序打印一个整数的每一位

void print_digit(int n)
{
    //如何得到每一位-->n%10

    //if (n > 0)
    //{
    //    printf("%d ", n % 10);
    //    print_digit(n / 10); //能得到，但是逆序
    //}
    //else
    //{
    //    printf("\n");
    //}

    //int m = 0;
    //scanf("%d", &m);
    //while (m != 0)
    //{
    //    printf("%d ", m % 10); //能得到，但是逆序
    //    m /= 10;
    //}
    

    //print(1234)
    //print(123) + 4
    //print(12) + 3 + 4
    //print(1) + 2 + 3 + 4
    if (n > 9)
    {
        print_digit(n / 10);
    }
    printf("%d ", n % 10);

}

//================================================

//求第n个斐波那契数（前两个数相加等于第三个数 1 1 2...）
/*
            n                       (n <= 2)           
Fib(n) = 
            Fib(n-1) + Fib(n-2)     (n > 2)
*/

int Fib(int n)
{
    if (n <= 2)
    {
        return 1;
    }
    else
    {
        return Fib(n - 1) + Fib(n - 2);//当n很大时，有大量重复计算，占用大量资源，效率极其低下
    }
}

int Fib_2(int n)
{
    int a = 1;
    int b = 1;
    int c = 0;
    int i = 0;

    if (n <= 2)
    {
        return 1;
    }
    else
    {
        for (i = 2; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
    
}
